Stirling Number

집합 분할 문제

집합을 몇개의 그룹으로 분할하는 경우의 수를 어떻게 구할 수 있을까?

Dynamic Programming.을 이용하면, 간단하다.
집합의 원소가 a, b, c, d, e, f, g, h, i, j 로 총 10개라 하자.
이들 원소 10개를 4개의 그룹으로 분할하는 경우의 수를 구하라는 문제는
a 제외 9개의 문자를 네 그룹으로 나누고, a를 배치하는 경우의 수 + a 제외 9개의 문자를 세 그룹으로 나누고 a 홀로 그룹이 되는 경우의 수를 구하라는 문제와 동치이다.

따라서 원소 수를 n, 나눠야 할 그룹 수를 k라 할 때, 경우의 수를 S(n, k)라 하면,
$S(10,4)=S(9,4)\times 4+S(9,3)$ 이 된다.

이러한 S(n, k)를 제 2종 스털링 수라 부른다.

Catalan Number

다각형 삼각분할 문제

정다각형을 몇개의 삼각형들로 분할하는 경우의 수를 어떻게 구할 수 있을까?

먼저, 카탈란 수에 대해 알아보자.
$C_0=1$일 때, n번째 카탈란 수 $C_n$은 아래와 같은 점화식으로써 정의된다.
$C_n=C_0{C}_{n-1}+C_1{C}_{n-2}+C_2{C}_{n-3}+\cdots +C_{n-3}{C}_2+C_{n-2}{C}_1+C_{n-1}{C}_0$
식의 재귀적 꼴만 봐도, 이 또한 Dynamic Programming.과 관계된다는 것을 느낄 수 있다.

n각형의 변은 n개이다. 그중 한 변 $\overline{S_1{S}_n}$을 포함하는 삼각형의 또 다른 한 점을 X라 하자.
$X=S_2\text{ 일 때, (분할의 경우의 수)}=(1)\times \text{(n-1각형 분할의 경우의 수)}$
$X=S_3\text{ 일 때, (분할의 경우의 수) = (3각형 분할의 경우의 수)}\times \text{((n-2)각형 분할의 경우의 수)}$
$X=S_4\text{ 일 때, (분할의 경우의 수) = (4각형 분할의 경우의 수)}\times \text{((n-3)각형 분할의 경우의 수)}$
...
$X=S_{n-1}\text{ 일 때, (분할의 경우의 수) = (n-1각형 분할의 경우의 수)}\times (1)$
이다.

따라서, 총 n-2개의 항이 탄생하며, n각형의 삼각분할은 $C_{n-2}$라는 사실을 알 수 있다. (* $C_1$ 또한 1이다.)

올바른 괄호 쌍 배열 문제

n쌍의 소괄호들을 올바르게 표현하는 서로 다른 경우의 수는 어떻게 구할 수 있을까?

카탈란 수가 동적계획법에 기반한다는 사실을 떠올리면, 문제해결 전략을 은근히 쉽게 세울 수 있다.

처음은 항상 '('로 시작할 것이다. 그리고 언젠간 닫힐 것이다. 이 한쌍의 소괄호가 언제 닫힐지는 알 수 없지만 있다고 하자. 그대로 나열하면 다음과 같은 형식이 된다. xxx, yyy는 그 자리에 뭐가 올지 알 수 없다는 의미이다.

'( xxx ) yyy' 이렇게 두면 카탈란 수를 사용할 준비가 끝났다.
괄호 쌍 n개의 배열 경우의 수는,
(xxx에 괄호 쌍 0개인 경우의 수) + (yyy에 괄호 쌍 n-1개인 경우의 수)
(xxx에 괄호 쌍 1개인 경우의 수) + (yyy에 괄호 쌍 n-2개인 경우의 수)
(xxx에 괄호 쌍 2개인 경우의 수) + (yyy에 괄호 쌍 n-3개인 경우의 수)
...
(xxx에 괄호 쌍 n-1개인 경우의 수) + (yyy에 괄호 쌍 0개인 경우의 수)
을 모두 더한 값이다.

따라서, 총 n개의 항이 탄생하며, 괄호 쌍 n개 배열 경우의 수는 $C_n$임을 알 수 있다.

교란순열Derangements

모든 요소가 자신의 초기 순서와 중복되지 않는 순열을 의미한다. (순열이란, 초기 순서가 있을 때, 존재하는 모든 순서를 가진 나열들의 표현이다.)

순열과 달리 자신의 초기 상태도 세지 않기 때문에, $D_1=0$이다.

교란순열이 이와 같은 점화식으로 표현되는 이유는, 다음과 같다.

포틀럭 파티를 연다고 하자. 사람 1부터 10까지 열명의 사람이 모였다.
1이 2의 음식을 가져갈 때, 2는 1의 음식을 가져가지 않거나 가져간다.
가져가지 않는다면, 이것은 1을 제외한 나머지 아홉명의 교란순열과 동치이다.
가져간다면, 이것은 1과 2를 제외한 나머지 여덟명의 교란순열과 동치이다.